FIPS 186-4

D.3 正規基底 Normal Bases

算術演算は以下のように実行される。

加算 Addition: 2 つの元を加算する処理は、2 を法とするビット単位の加算によって実行される。したがって、例えば、

$ (1100111) + (1010010) = (0110101)

$ a=(a_0\:a_1\:...\:a_{m-1})

then

$ a^2 = (a_{m-1}\:a_0\:a_1\:...\:a_{m-2})

乗算: 乗算を実行するために、入力に対して関数F(u,v)が構築される。

$ \underline{u} = (u_0\:u_1\:...\:u_{m-1}) \: \mathsf{and} \: \underline{v} = (v_0\:v_1\:...\:v_{m-1})

次のように:

2. u を p を法とする T 位数の整数とします。

3.2 For j from 0 to T-1 do

3.2.1 Set n ← w.

3.2.2 For i=0 to m-1 do

3.2.2.1 Set F(n)←i.

3.2.2.2 Set n←2n mod p.

3.2.3 Set w ← uw mod p.

4. 次の数式を出力します。

$ F(u,v) := \sum^{p-2}_{k=1}u_{F(k+1)}v_{F(p-k)}

この計算は基底ごとに1回だけ実行する必要があります。

Bの関数Fが与えられている場合、積は

$ (c_0\:c_1\:...\:c_{m-1})=(a_0\:a_1\:...\:a_{m-1})*(b_0\:b_1\:...\:b_{m-1})

次のように計算されます。

3.1 Compute

$ c_k = F(\underline{u},\underline{v})

$ F(1)=0\quad F(8)=3\quad\,\,\, F(15)=6\quad F(22)=5

$ F(2)=1\quad F(9)=3\quad\,\,\, F(16)=4\quad F(23)=6

$ F(3)=5\quad F(10)=2\quad F(17)=0\quad F(24)=1

$ F(4)=2\quad F(11)=4\quad F(18)=4\quad F(25)=2

$ F(5)=1\quad F(12)=0\quad F(19)=2\quad F(26)=5

$ F(6)=6\quad F(13)=4\quad F(20)=3\quad F(27)=1

$ F(7)=5\quad F(14)=6\quad F(21)=3\quad F(28)=0

したがって、

$ F(\underline{u},\underline{v})=u_0v_1+u_1(v_0+v_2+v_5+v_6)+u_2(v_1+v_3+v_4+v_5)+u_3(v_2+v_5)+

$ u_4(v_2+v_6)+u_5(v_1+v_2+v_3+v_6)+u_6(v_1+v_4+v_5+v_6)

したがって、もし

$ a=(1\,0\,1\,0\,1\,1\,1)\,{\tt and}\, b=(1\,1\,0\,0\,0\,0\,1))

then

$ c_0=F((1\,0\,1\,0\,1\,1\,1),(1\,1\,0\,0\,0\,0\,1))=1,

$ c_1=F((0\,1\,0\,1\,1\,1\,1),(1\,0\,0\,0\,0\,1\,1))=0,

$ \vdots

$ c_6=F((1\,1\,0\,1\,0\,1\,1),(1\,1\,1\,0\,0\,0\,0))=1,